# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        node = head
        n = 0
        while node:
            n += 1
            node = node.next
        if n == 1:
            return True
        right_index = n // 2
        head_node = ListNode(0, head)
        prev = head_node
        node = head
        for i in range(right_index):
            next_node = node.next
            node.next = prev
            prev = node
            node = next_node
        right_head = next_node
        virtual_left = ListNode(0, prev)
        prev = virtual_left
        left_node = virtual_left.next
        prev.next = None
        if n % 2 == 0:
            right_node = right_head
        else:
            right_node = right_head.next
        flag = True
        while right_node:
            if flag and left_node.val != right_node.val:
                flag = False
            right_node = right_node.next
            next_node = left_node.next
            left_node.next = prev
            prev = left_node
            left_node = next_node
        node = prev
        while node.next.next:
            node = node.next
        node.next = right_head
        return flag


data = Solution()
head = ListNode(1)
node1 = ListNode(2)
node2 = ListNode(2)
node3 = ListNode(1)
head.next = node1
node1.next = node2
node2.next =node3
print(data.isPalindrome(head))